백준 2239번
오늘 풀어본 문제는 백준의 2239번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
스도쿠는 매우 간단한 숫자 퍼즐이다. $9 \times 9$ 크기의 보드가 있을 때, 각 행과 각 열, 그리고 $9$ 개의 $3 \times 3$ 크기의 보드에 $1$ 부터 $9$ 까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 $1$ 부터 $9$ 까지의 숫자가 중복 없이 나오고, 각 열에 $1$ 부터 $9$ 까지의 숫자가 중복 없이 나오고, 각 $3 \times 3$ 짜리 사각형($9$ 개이며, 위에서 색깔로 표시되었다)에 $1$ 부터 $9$ 까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
입력
$9$ 개의 줄에 $9$ 개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 $0$ 이 주어진다.
출력
$9$ 개의 줄에 $9$ 개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, $81$ 자리의 수가 제일 작은 경우를 출력한다.
풀이과정
1번째 시도
문제를 보고 백트래킹을 이용해야 하는 문제임을 알 수 있었다. 우선 search 함수를 재귀함수 형태로 만들어 한 칸씩 나아가며 모든 경우를 조사하게 했다.
같은 행과 열, 또는 $3 \times 3$ 칸에서 이미 발견 된 수는 candidate 배열의 값에서 false 로 설정하고, true 인 것들만 순회하며 탐색을 하도록 하였다. 이 때, 순서를 잘 설정해주어 가장 먼저 발견된 결과가 사전순에서 제일 앞선 결과가 되도록 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> sudoku(9, vector<int>(9, 0));
bool search(int currX, int currY);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0; i<9; i++) {
string line;
cin >> line;
for (int j=0; j<9; j++) {
sudoku[i][j] = line[j] - '0';
}
}
search(0, 0);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
cout << sudoku[i][j];
}
cout << "\n";
}
return 0;
}
bool search(int currX, int currY) {
bool candidate[9];
for (int i=0; i<9; i++) {
candidate[i] = true;
}
int nextX = currX;
int nextY = currY + 1;
nextX += (nextY / 9);
nextY %= 9;
if (nextX == 9) {
return true;
}
if (sudoku[currX][currY] == 0) {
for (int i=0; i<9; i++) {
int value = sudoku[i][currY];
if (value == 0) {
continue;
}
candidate[value - 1] = false;
}
for (int j=0; j<9; j++) {
int value = sudoku[currX][j];
if (value == 0 || currY == j) {
continue;
}
candidate[value - 1] = false;
}
int centerX = (currX / 3) * 3 + 1;
int centerY = (currY / 3) * 3 + 1;
for (int i=-1; i<=1; i++) {
for (int j=-1; j<=1; j++) {
int aroundX = centerX + i;
int aroundY = centerY + j;
int value = sudoku[aroundX][aroundY];
if (currX == aroundX && currY == aroundY) {
continue;
}
candidate[value - 1] = false;
}
}
}
else {
return search(nextX, nextY);
}
for (int i=0; i<9; i++) {
if (candidate[i]) {
sudoku[currX][currY] = i + 1;
if (search(nextX, nextY)) {
return true;
}
}
}
sudoku[currX][currY] = 0;
return false;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
왜 틀렸는지 이해가 안 가서 게시판을 둘러보았고, 출력 양식에 문제가 있어 틀린 사람들이 있다는 것을 알 수 있었다. 그러나 나는 띄어쓰기를 고려하였는데도 틀렸기 때문에, 마지막 개행 문자가 문제를 일으키나 싶어 마지막에는 개행 문자를 출력하지 않도록 설정하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> sudoku(9, vector<int>(9, 0));
bool search(int currX, int currY);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0; i<9; i++) {
string line;
cin >> line;
for (int j=0; j<9; j++) {
sudoku[i][j] = line[j] - '0';
}
}
search(0, 0);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
cout << sudoku[i][j];
}
if (i < 8) {
cout << "\n";
}
}
return 0;
}
bool search(int currX, int currY) {
bool candidate[9];
for (int i=0; i<9; i++) {
candidate[i] = true;
}
int nextX = currX;
int nextY = currY + 1;
nextX += (nextY / 9);
nextY %= 9;
if (nextX == 9) {
return true;
}
if (sudoku[currX][currY] == 0) {
for (int i=0; i<9; i++) {
int value = sudoku[i][currY];
if (value == 0) {
continue;
}
candidate[value - 1] = false;
}
for (int j=0; j<9; j++) {
int value = sudoku[currX][j];
if (value == 0 || currY == j) {
continue;
}
candidate[value - 1] = false;
}
int centerX = (currX / 3) * 3 + 1;
int centerY = (currY / 3) * 3 + 1;
for (int i=-1; i<=1; i++) {
for (int j=-1; j<=1; j++) {
int aroundX = centerX + i;
int aroundY = centerY + j;
int value = sudoku[aroundX][aroundY];
if (currX == aroundX && currY == aroundY) {
continue;
}
candidate[value - 1] = false;
}
}
}
else {
return search(nextX, nextY);
}
for (int i=0; i<9; i++) {
if (candidate[i]) {
sudoku[currX][currY] = i + 1;
if (search(nextX, nextY)) {
return true;
}
}
}
sudoku[currX][currY] = 0;
return false;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
3번째 시도
한참을 코드와 사투를 한 끝에, 탐색이 끝나는 조건을 잘못 설정했음을 알 수 있었다. nextX == 9 라는 조건은 마지막 칸에서 숫자를 제대로 탐색하지 않고 즉시 종료되게 했던 것이다. 올바른 조건은 currX == 9 였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> sudoku(9, vector<int>(9, 0));
bool search(int currX, int currY);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0; i<9; i++) {
string line;
cin >> line;
for (int j=0; j<9; j++) {
sudoku[i][j] = line[j] - '0';
}
}
search(0, 0);
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
cout << sudoku[i][j];
}
if (i < 8) {
cout << "\n";
}
}
return 0;
}
bool search(int currX, int currY) {
bool candidate[9];
for (int i=0; i<9; i++) {
candidate[i] = true;
}
int nextX = currX;
int nextY = currY + 1;
nextX += (nextY / 9);
nextY %= 9;
if (currX == 9) {
return true;
}
if (sudoku[currX][currY] == 0) {
for (int i=0; i<9; i++) {
int value = sudoku[i][currY];
if (value == 0) {
continue;
}
candidate[value - 1] = false;
}
for (int j=0; j<9; j++) {
int value = sudoku[currX][j];
if (value == 0 || currY == j) {
continue;
}
candidate[value - 1] = false;
}
int leftTopX = (currX / 3) * 3;
int leftTopY = (currY / 3) * 3;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
int aroundX = leftTopX + i;
int aroundY = leftTopY + j;
int value = sudoku[aroundX][aroundY];
if (currX == aroundX && currY == aroundY) {
continue;
}
candidate[value - 1] = false;
}
}
}
else {
return search(nextX, nextY);
}
for (int i=0; i<9; i++) {
if (candidate[i]) {
sudoku[currX][currY] = i + 1;
if (search(nextX, nextY)) {
return true;
}
}
}
sudoku[currX][currY] = 0;
return false;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
CLASS 5 문제들은 거의 패턴이 일정한 것 같다. 우선 딱 봐도 지치는 문제를 던져놓고, 힘들게 구현하면, 테스트 케이스는 잘 작동한다. 그러나, 막상 제출을 해보면 틀리거나 시간 초과가 발생한다. 겨우겨우 찾아낸 잘못된 부분은 어이없을 정도로 사소한 부분이다.
코딩을 할 때 좀 더 주의를 기울일 필요가 있을 것 같다. 앞으로의 CLASS 5 여정이 점점 걱정되기 시작한다…
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2239